package Vaanee;



use vaaneeConfig qw(%C);
use Varg qw(%C);
use DepTree qw(%C);
use Align qw(%C);
use Features qw(%dbs %C);  

use AlignBeam qw(%C);
use Parameters qw(%C);
use LocalBeam qw(%C);

use PQ qw();

@ISA = qw(Exporter);
@EXPORT = qw();
@EXPORT_OK = qw(%dbs %C);


sub new {
	my($corpus) = {};
	my($classname) = shift;
	bless($corpus);

	my($srcFile) = shift;
	my($tgtFile) = shift;
	my($srcDep) = shift;
	my($srcAlign) = shift;

	my($line);

	# Temporary variables
	my($a,$b,$c);

	my($sennum,$word,@words,@temparr,$tempsca);

	my($Varg,$Align,$AlignBeam,$Features,$Dep);

	my(@tempalns);
	my($i,$j,$k);
	my($srcword,$tgtword);
	my(%sentencenums);
	
	if($srcFile) {
		print STDERR "Loading Sens\n";
		$corpus->loadSen('SSen',$srcFile);
	}

	if($tgtFile) {
		print STDERR "Loading Tgt Sens\n";
		$corpus->loadSen('TSen',$tgtFile);
	}

	if($srcDep) {
		print STDERR "Loading Deps\n";
		$corpus->loadDep('SDep',$srcDep);
	}

	if($srcAlign) {
		print STDERR "Loading Aligns\n";
		$corpus->loadAlign('Align',$srcAlign);
	}

	# Add the gold features

	if($srcAlign ne "")
	{
		print STDERR "Adding Gold Node Features\n";
		$corpus->addGoldnodeFeats('nodeFeatures');

		print "Adding Gold Sentence Features\n";

		$corpus->addGoldsenFeats('SFeatures');
	}
	
	return $corpus;
}

sub addGoldnodeFeats {
	my $corpus = shift;
	my $type = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		print STDERR "Adding gold node feats for Sentence: $senNum\n";
		for($i=0;$i<@{$corpus->{$senNum}->{'SSen'}};$i++) {

			my $Features;

			$Features = new Features;
			$Features->getnodeFeatures($i,$corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
						      $corpus->{$senNum}->{'SDep'},$corpus->{$senNum}->{'Align'},"u");

			$corpus->{$senNum}->{$type}->[$i] = $Features;
#			$Features->print();


		}
	}

	
	return $corpus;
}

sub addGoldsenFeats {
	my $corpus = shift;
	my $type = shift;
	my($Parameters) = shift;
	my $senNum ;
	my $i,$j;

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {

			my $Features;

			print STDERR "Adding gold node feats for Sentence: $senNum\n";

			$Features = new Features;
			$Features->getsenFeatures($corpus->{$senNum}->{'SSen'},$corpus->{$senNum}->{'TSen'},
						    $corpus->{$senNum}->{'SDep'},$corpus->{$senNum}->{'Align'},"u");

			$corpus->{$senNum}->{$type} = $Features;

			#print "Adding SEN Feats of $senNum\n";
			#$Features->print();

	}

	return $corpus;
}

sub loadSen {

	my($corpus) = shift;
	my($type) = shift;
	my($file) = shift;

	open(FILE,$file);

	my @lines = <FILE>;
	chomp(@lines);

	my $no_lines = @lines;
	my $senNum ;
	my $i=0;
	my $wordnum = 0;
	if($flag eq "i")
	{

		for($i=0; $i < $no_lines; $i++)
		{
			if($lines[$i] =~ /^\s*$/)
			{
			}
			elsif($lines[$i] =~ /^([0-9]+)$/)
			{
				$senNum = $1;
				$wordnum = 0;
			}
			else
			{
				my($word_POS_root,@features) = split(/\t/,$lines[$i]);

				my($word,$pos,$root) = split(/_/,$word_POS_root);
				<< '#';
				my(@letters) = split(//,$word);
				my($prefix4) = $letters[-4].$letters[-3].$letters[-2].$letters[-1];
				my($prefix3) = $letters[-3].$letters[-2].$letters[-1];
				my($prefix2) = $letters[-2].$letters[-1];
				my($prefix1) = $letters[-1];
				my($suffix4) = $letters[0].$letters[1].$letters[2].$letters[3];
				my($suffix3) = $letters[0].$letters[1].$letters[2];
				my($suffix2) = $letters[0].$letters[1];
				my($suffix1) = $letters[0];
#
				$corpus->{$senNum}->{$type}->[$wordnum]->{'word'} = $word;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'pos'} = $pos;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'root'} = $root;

				<< '#';
				$corpus->{$senNum}->{$type}->[$wordnum]->{'prefix4'} = $prefix4;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'prefix3'} = $prefix3;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'prefix2'} = $prefix2;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'prefix1'} = $prefix1;

				$corpus->{$senNum}->{$type}->[$wordnum]->{'suffix4'} = $suffix4;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'suffix3'} = $suffix3;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'suffix2'} = $suffix2;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'suffix1'} = $suffix1;
#

# For 'prep' and 'aux' of the word. 

				my $feature;
				foreach $feature (@features)
				{
					my ($feat,$value) = split(/:/,$feature); 
					$corpus->{$senNum}->{$type}->[$wordnum]->{$feat} = $value;
				}
				$wordnum++;
			}
		}
	}
	else
	{
		for($i=0; $i < $no_lines; $i++)
		{
#                       print $lines[$i]."\n";
			$senNum = $i + 1;
			$wordnum = 0;
			@words = split(/\s+/,$lines[$i]);
			foreach $word_POS_root (@words)
			{
				my($word,$pos,$root) = split(/_/,$word_POS_root);
				$corpus->{$senNum}->{$type}->[$wordnum]->{'word'} = $word;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'pos'} = $pos;
				$corpus->{$senNum}->{$type}->[$wordnum]->{'root'} = $root;

				$wordnum++;
			}
		}

	}
}

sub loadDep {

	my($corpus) = shift;
	my($type) = shift;
	my($depfname) = shift;
	my($senNum);
	
	open(DEPTREE,$depfname);
	my($depline);
	my($procsen) = 0;
	my($senidx,$rootpos) ;
	my($Senid) = 1;

	while($depline=<DEPTREE>)
	{
		chomp($depline);
##		CHANGE MADE BY SRIRAM Aug 7, 08
		$senNum = eval($depline)+1;
		print "SenNum = ".$senNum."\n";

		my($Dep) = new DepTree;

		my $line = <DEPTREE>;
		chomp($line);
		($temp,$root_pos) = split(/\s+/,$line);

		$Dep->addroot($root_pos);

		while(!($line=~/^\s*$/))
		{
			$line = <DEPTREE>; chomp($line);

			if($line=~/^[#](.*?) (.*)$/)
			{
				$word_num = $1;
				$Dep->createnode($word_num);

				$line = <DEPTREE>;  chomp($line);
			}
			elsif($line=~/pos: (.*)/) {
				$Dep->addpos($word_num,$1);
			}
			elsif($line=~/rel: (.*)/) {
				$Dep->addrel($word_num,$1);
			}
			elsif($line=~/role: (.*)/) 
			{
#				print $1."\n";
				$Dep->addrole($word_num,$1);
			}
			elsif($line=~/att #(.*)/)
			{
				$Dep->addattch($word_num,$1);
			}
			if($line=~/^[&](.*?)$/)   #Ask Karthik to check this
			{
				$word_num = $1;

				$line = <DEPTREE>;  chomp($line);

				$Dep->createnode($word_num);
			}
			elsif($line=~/con #(.*)/)
			{
				$Dep->addattch($word_num,$1);
			}
		}

		$corpus->{$senNum}->{$type} = $Dep;
	}
}

sub loadAlign {
	my($corpus) = shift;
	my($type) = shift;
	my($file) = shift;

	open(FILE,$file) || die "Can't open $file\n";
	my @lines = <FILE>;

	my($line);
	my $no_lines = @lines;
	my $senNum;
	my $i=0;
	my $wordnum = 0;
	my $alignments;
	
	for($i=0; $i < $no_lines; $i++)
	{
		$line = $lines[$i]; 
		($senNum,$srcword,$tgtword,$strength) = split(/\s+/,$line);
		$alignments->{$senNum}->{"$srcword $tgtword"} = $strength+1;

	}

	foreach $senNum (keys %{$alignments}) {
		my $Align = new Align;

		foreach $line (keys %{$alignments->{$senNum}}) {
			($srcword,$tgtword) = split(/\s+/,$line);
			$Align->addalign($srcword,$tgtword);
		}

		$corpus->{$senNum}->{$type} = $Align; 

	}
}

sub predictAndupdate2 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	
	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};


	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
#	print STDERR "words($nengwords):".scalar($nhinwords)."\n\n";
	$starttime = time();

	my($obj,$priorIty);

#	$GoldAlign->printAln($engsen,$hinsen);
	$corpus->predictAndupdatenode($senNum,$Dep->[0]->{'root'},$Parameters,$ifUpdate);

}


sub predictAndupdatenode
{
	my($corpus) = shift;
	my($senNum) = shift;
	my($nodeId) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

	#print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priorIty);


	#Getting the Local beam of nodeId
	$localpq = new PQ;

	for($k=0;$k<=$nhinwords;$k++) # here K == nhinwords for src going to NULL
	{

		my @candwords;
		if($k!=$nhinwords)
		{ push(@candwords,$k); }

		$LFeatures = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score=$score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	for($k=0;$k<$nhinwords-1;$k++) {

		my @candwords;
		push(@candwords,$k); 
		push(@candwords,$k+1);

		$LFeatures = new Features;
		$LFeatures->getnodeLFeatures($nodeId,$engsen,$hinsen,\@candwords,"p");

		$score = $Parameters->getScore($LFeatures);

		#print "Alignment between $nodeId -> ".join('_',@candwords)." score = $score\n";
		#$LFeatures->print();

		$localpq->push_heap(\@candwords,$score);
	}

	$localbeam = new LocalBeam($nhinwords);	
	$k=0;
	while(! $localpq->empty()) {
		($obj,$priority) = $localpq->pop_heap();

		$localbeam->[$k]->[0] = $priority;
		$localbeam->[$k]->[1] = $obj;
		$k++;
	}

	$localbeams{$nodeId} = $localbeam;

	foreach $child (@{$Dep->[$nodeId]->{'attch'}})
	{
		$localbeams{$child} = $corpus->predictAndupdatenode($senNum,$child,$Parameters,$ifUpdate);
		#print "CHILD = $child $localbeams{$child}...\n";
	}
		
	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns,$insertedKey) = ();

	$onePriority = 0;
	foreach $i (keys %localbeams)  #only the node and there children.
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		
	}

	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey = join('_',keys %{$oneAlign});
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
	#print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	for($k=0;$k<$C{'K'};$k++) 
	{

		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		$GenAlign = $Beam->[$k];
		#print "$k $GenAlign\n";

		foreach $i (keys %localbeams) 
		{
			my($hn);
			if($i == $nodeId) 
			{
				foreach $hn (@{$localbeams{$i}->[$oneAlign->{$i}]->[1]}) #?????
				{
					$GenAlign->addalign($i,$hn);
				}
			}
			else 
			{
				#$localbeams{$i}->[$oneAlign->{$i}]->[1]->print($engsen);
				$GenAlign->mergealign($engsen,$localbeams{$i}->[$oneAlign->{$i}]->[1]);
			}
			#$GenAlign->print($engsen);
		}
		$GenAlign->{'score'} = $onePriority;
		


		
		
		# Put in the Global Beam

		foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey = $newArr{$i}."_";    #?????????????????
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$nodeId}->[$newArr{$nodeId}]->[0] - $localbeams{$nodeId}->[$newArr{$nodeId}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}
	}



	my($reorderPQ) = new PQ;

	$corpus->{$senNum}->{'AlignBeam'} = $Beam;

	# Recalculate the scores
	#print "Final Scores\n";
	$GenAlign = new Align($nengwords);
	#print "Alignments in the Global Beams\n";
#	print "Predict Features of $nodeId\n";


	for($i=0;$i<$newK;$i++)
	{
		$Features = new Features;

		$Features->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"p");

#		$Features->print();
		

#		$corpus->{$senNum}->{$type}->[$nodeId] = $Features;
		$Beam->[$i]->{'score'} = $Parameters->getScore($Features);

		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'});
	}

	
#	print "Gold-----------------------------\n";
#	my $gold_features;
#	$gold_features = $corpus->{$senNum}->{'nodeFeatures'}->[$nodeId];
#	$gold_features->print();

	#-------------------------------Update Parameters:
	my($obj,$priority);
	my($localbeam);

	$localbeam = new LocalBeam($newK);

	my $PredFeatArray;
	my $mistakesArray;

	$i=0;

	# print "K-Best for Node $nodeId\n";
	#$corpus->{$senNum}->{'SFeatures'}->print();
#	$corpus->{$senNum}->{'Align'}->print($engsen);
	#print "Predictions..\n";
#	print "$senNum , Gold Features of $nodeId\n";
#	$corpus->{$senNum}->{'nodeFeatures'}->[$nodeId]->print();
	
	while(! $reorderPQ->empty()) {
		($obj,$priority) = $reorderPQ->pop_heap();

		$localbeam->[$i]->[0] = $priority;
		$localbeam->[$i]->[1] = $obj;

		#print "$i) $priority\n";
		$Beam->[$i] = $obj;
		#$Beam->[$i]->print($engsen);

		if($ifUpdate) {
			$Features = new Features;
			$Features->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[$i],"u");

#			if($i==0) {
#			print "Predict $i\n" ;
#			$Features->print() if($i==0);
#
#			print "Predicts after processing $nodeId\n";
#			$Beam->[$i]->printAln($engsen,$hinsen);
#			}

			$PredFeatArray->[$i] = $Features;
			$mistakeArray->[$i] = $GoldAlign->getnodeMistakes($nodeId,$Beam->[$i]);

		}
		$i++;
	}


	#print "Before $senNum...\n";
	#$Parameters->list();
	my($updatedParams);


	$Parameters->updateParams($corpus->{$senNum}->{'nodeFeatures'}->[$nodeId],$PredFeatArray,$mistakeArray,$newK) if($ifUpdate);
	#print "After $senNum...\n";
	#$Parameters->list();

	return $localbeam;
}

sub predictAndupdate1 {

	my($corpus) = shift;
	my($senNum) = shift;
	my($Parameters) = shift;
	my($ifUpdate) = shift;
	my($i);

	my($Varg,$Dep);
	my($engsen,$hinsen);
	my($GoldAlign,$GenAlign,$GenAlign2);
	my($Beam,$TempBeam);
	my($LFeatures,$score);
	my($localbeam,%localbeams);
	my($k,$m,$n,$p,$i);
	my($minScore,$minPosition);
	my($hinwordpos);
	my($verbnum,$argnum);
	my($LFeatures,$GenFeatures);
	my($nengwords,$nhinwords);

	$Dep = $corpus->{$senNum}->{'SDep'};
	$engsen = $corpus->{$senNum}->{'SSen'};
	$nengwords = @{$engsen};
	$hinsen = $corpus->{$senNum}->{'TSen'};
	$nhinwords = @{$hinsen};
	$GoldAlign = $corpus->{$senNum}->{'Align'};

	$corpus->{$senNum}->{'AlignBeam'} = new AlignBeam($C{'K'});
	$Beam = $corpus->{$senNum}->{'AlignBeam'};

	my($s);

#	print STDERR "$senNum) words($nengwords):".scalar($nhinwords);
	#print "words($nengwords):".scalar($nhinwords)."\n";
	$starttime = time();

	my($obj,$priority);
	for($i=0;$i<$nengwords;$i++)
	{
		$localpq = new PQ;


		for($k=0;$k<=$nhinwords;$k++) {

			my @candwords;
			if($k!=$nhinwords)
			{ push(@candwords,$k); }

			$LFeatures = new Features;
			$LFeatures->getnodeLFeatures($i,$engsen,$hinsen,\@candwords,"p");

			$score = $Parameters->getScore($LFeatures);

#			print "Alignment between $i -> ".join('_',@candwords)." score=$score\n";
#			$LFeatures->print();

			$localpq->push_heap(\@candwords,$score);
		}
		for($k=0;$k<$nhinwords-1;$k++) {

			my @candwords;
			push(@candwords,$k); 
			push(@candwords,$k+1);

			$LFeatures = new Features;
			$LFeatures->getnodeLFeatures($i,$engsen,$hinsen,\@candwords,"p");

			$score = $Parameters->getScore($LFeatures);

#			print "Alignment between $i -> ".join('_',@candwords)." score = $score\n";
#			$LFeatures->print();

			$localpq->push_heap(\@candwords,$score);
		}

		$localbeam = new LocalBeam($nhinwords);	
		$k=0;
		while(! $localpq->empty()) {
			($obj,$priority) = $localpq->pop_heap();

#			if($i==0) {
#				print "$priority ".join('_',@{$obj})."\n";
#			}

			$localbeam->[$k]->[0] = $priority;
			$localbeam->[$k]->[1] = $obj;
			$k++;
		}

		$localbeams{$i} = $localbeam;
	}		

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " sort:$duration";

	my($globalPQ) = new PQ;

	my($oneAlign);
	my($onePriority);

	my(%insertedAligns,$insertedKey) = ();

	$onePriority = 0;
	foreach $i (keys %localbeams)
	{
		$oneAlign->{$i} = 0;
		$onePriority += $localbeams{$i}->[0]->[0];		
	}

	$globalPQ->push_heap($oneAlign,$onePriority);
	$insertedKey = join('_',keys %{$oneAlign});
	$insertedAligns{"$insertedKey"} = 1;

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " init:$duration";

	my($newK);
	$newK = $C{'K'};

	for($k=0;$k<$C{'K'};$k++) {
		
		my($oneAlign);
		if($globalPQ->empty()) {
			$newK = $k;
			last;
		}

		($oneAlign,$onePriority) = $globalPQ->pop_heap();

		#print "\n$onePriority: ".join(' ',%{$oneAlign})."\n";

		$GenAlign = $Beam->[$k];
		#print "$k $GenAlign\n";
		foreach $i (keys %localbeams) {
			my($hn);
			foreach $hn (@{$localbeams{$i}->[$oneAlign->{$i}]->[1]}) {
				$GenAlign->addalign($i,$hn);
			}
		}
		$GenAlign->{'score'} = $onePriority;
		#print "Score $onePriority\n";

		# Put in the Global Beam

	       foreach $i (keys %localbeams) {

			my(%newArr) = %{$oneAlign};
			my($newPriority);

			$newArr{$i} = $newArr{$i}+1;

			my($key);
			foreach $key (sort {$a<=>$b} keys %newArr) {
				$insertedKey = $newArr{$i}."_";
			}
			$insertedKey =~s/_$//g;

			if(! $insertedAligns{"$insertedKey"}) {

				$newPriority = $onePriority + $localbeams{$i}->[$newArr{$i}]->[0] - $localbeams{$i}->[$newArr{$i}-1]->[0];
				$globalPQ->push_heap(\%newArr,$newPriority);
				$insertedAligns{"$insertedKey"} = 1;
			}
		}

	}


	$time=time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " kbest:$duration";

	$corpus->{$senNum}->{'Align'}->{'score'} = $Parameters->getScore($corpus->{$senNum}->{'SFeatures'});


	my($reorderPQ) = new PQ;

	$corpus->{$senNum}->{'AlignBeam'} = $Beam;
	
	# Recalculate the scores
	#print "Final Scores\n";
	$GenAlign = new Align($nengwords);
	#print "Alignments in the Global Beams\n";


	for($i=0;$i<$newK;$i++)
	{
		$Features = new Features;
		$Features->getsenFeatures($engsen,$hinsen,$Dep,$Beam->[$i],"u");
		
		$Beam->[$i]->{'score'} = $Parameters->getScore($Features);

		$reorderPQ->push_heap($Beam->[$i],$Beam->[$i]->{'score'});
	}

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " reranking-pushheap:$duration";

	my($obj,$priority);

	my $PredFeatArray;
	my $mistakesArray;

	$i=0;
	
	#print "K-Best for Sentence $senNum\n";
#	print "GOLD FEATURES & ALIGNMENT\n";
#	$corpus->{$senNum}->{'SFeatures'}->print();
#	$corpus->{$senNum}->{'Align'}->printAln($engsen,$hinsen);
#	for($nodeId=0;$nodeId<@$engsen;$nodeId++) {
#		my($Feat) = new Features;
#		$Feat->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$GoldAlign,"p");
#		print "Node $engsen->[$nodeId]->{'word'} features..\n";
#		$Feat->print();
#		print "---\n";
#	}
	
	#print "Predictions..\n";
	while(! $reorderPQ->empty()) {
		($obj,$priority) = $reorderPQ->pop_heap();

		#print "$i) $priority\n";
		$Beam->[$i] = $obj;
		#$Beam->[$i]->print($engsen);

		if($ifUpdate) {
			$Features = new Features;
			$Features->getsenFeatures($engsen,$hinsen,$Dep,$Beam->[$i],"u");

			#$Features->print();

			$PredFeatArray->[$i] = $Features;
			$mistakeArray->[$i] = $GoldAlign->getMistakes($Beam->[$i]);

			#print "Mistakes = $mistakeArray->[$i]\n";
		}
		$i++;
	}

#	print "---------------------\n";
#	print "BEST PREDICTIONS ...\n";
#	$PredFeatArray->[0]->print();
#	$Beam->[0]->printAln($engsen,$hinsen);
#	for($nodeId=0;$nodeId<@$engsen;$nodeId++) {
#		my($Feat) = new Features;
#		$Feat->getnodeFeatures($nodeId,$engsen,$hinsen,$Dep,$Beam->[0],"p");
#		print "Node $engsen->[$nodeId]->{'word'} features..\n";
#		$Feat->print();
#		print "---\n";
#	}

#	print "---------------------\n";
#


	#print "Before $senNum...\n";
	#$Parameters->list();
	my($updatedParams);

	$Parameters->updateParams($corpus->{$senNum}->{'SFeatures'},$PredFeatArray,$mistakeArray,$newK) if($ifUpdate);
	#print "After $senNum...\n";
	#$Parameters->list();

#	print "New Gold Score = ".$Parameters->getScore($corpus->{$senNum}->{'SFeatures'})."\n";;
#	print "New Pred0 Score = ".$Parameters->getScore($PredFeatArray->[0])."\n\n";

	$time = time();
	$duration = $time - $starttime;
	$starttime = $time;
#	print STDERR " reranking-popheap:$duration\n";


	#print "Printing Beam in the final state\n";
	#for($i=0;$i<$C{'K'};$i++)
	#{
	#	$Beam->[$i]->print($corpus->{$senNum}->{'SSen'});
	#}
	#print "Done\n\n\n";
	
	return ($newK,$updatedParams);
}

sub updateparams {
	my($this) = shift;
	my($Parameters) = shift;
	my($j) = shift;
	my($K) = shift;
	my($updateoption) = shift;

	my(@b,$lam_dist,@dist);
	my($k);	
	my($Align,$GenAlign);
	my($Features,$GFeatures,$GenFeatures,$GenFeatures2);
	my($gscore) ;
	my(@alpha);

	$Align = $this->[$j]->{'Align'};
	$Varg = $this->[$j]->{'Varg'};
	$Dep = $this->[$j]->{'SDep'};
	$engsen = $this->[$j]->{'SSen'};
	$hinsen = $this->[$j]->{'TSen'};
	$GoldAlign = $this->[$j]->{'Align'};
	$Beam = $this->[$j]->{'AlignBeam'};

	$Features = $this->[$j]->{'Features'};
	$GFeatures = $this->[$j]->{'GFeatures'};
	$gscore = $Parameters->getScore($Features);

	for($k=0;$k<$K;$k++)
	{
		$GenAlign = $Beam->[$k];
		$GenFeatures = new Features;
		$GenFeatures2 = new Features;

		if($updateoption eq "a")
		{ 
			$GenFeatures->getFeatures($engsen,$hinsen,$GenAlign,$Varg,$Dep); 
			$GenFeatures2->difffeatures($Features,$GenFeatures);
		}
		else
		{ 
			$GenFeatures->getGFeatures($engsen,$hinsen,$GenAlign,$Varg,$Dep); 
			$GenFeatures2->difffeatures($GFeatures,$GenFeatures);
		}

=cut
		foreach $feat (keys %{$GenFeatures}) {
			print "$feat($GenFeatures->{$feat}) ";
		}
		print "\n";

		foreach $feat (keys %{$GenFeatures2}) {
			print "$feat($GenFeatures2->{$feat}) ";
		}
		print "\n\n";
=cut
		
		$lam_dist[$k] = $gscore - $this->[$j]->{'AlignBeam'}->[$k]->{'score'};
		$b[$k] = $Align->getMistakes($GenAlign);
		$b[$k] -= $lam_dist[$k];	
	
		$dist[$k] = $GenFeatures2;

		$b[$k] -= $lam_dist[$k];
		#print "B array = $b[$k]\n";
	}

	@alpha = &hildreth($K,\@dist,\@b);

	for($k=0;$k<$K;$k++)
	{
		$GenFeatures = $dist[$k];
		foreach $feat (keys %$GenFeatures)
		{
			$Parameters->{$feat} += $alpha[$k]*$GenFeatures->{$feat};
		}
	}
}

sub hildreth {
	my($K) = shift;
	my($a) = shift;
	my($b) = shift;

	my($i);
	my($max_iter) = 10000;
	my($eps) = 0.00000001;
	my($zero) = 0.000000000001;

	my(@alpha,@F,@kkt);
	my($max_kkt) = -1000000;

	my(@A);
	my(@is_computed);

	for($i=0;$i<$K;$i++)
	{
		$A[$i][$i] = Features::dotProduct($a->[$i],$a->[$i]);
		$is_computed[$i] = 0;
	}

	my($max_kkt_i) = -1;

	for($i=0;$i<$K;$i++)
	{
		$F[$i] = $b->[$i];
		$kkt[$i] = $F[$i];
		if($kkt[$i]>$max_kkt) { $max_kkt = $kkt[$i]; $max_kkt_i = $i; }
	}

	my($iter) = 0;
	my($diff_alpha) = 0;
	my($try_alpha) = 0;
	my($add_alpha) = 0;


	while($max_kkt >= $eps && $iter<$max_iter)
	{
		if($A[$max_kkt_i][$max_kkt_i] <= $zero)
		{
			$diff_alpha = 0.0
		}	
		else
		{
			$diff_alpha = $F[$max_kkt_i]/$A[$max_kkt_i][$max_kkt_i];
		}

		$try_alpha = $alpha[$max_kkt_i] + $diff_alpha;
		$add_alpha = 0.0;

		if($try_alpha < 0.0)
		{
			$add_alpha = -1.0 * $alpha[$max_kkt_i];
		}
		else
		{
			$add_alpha = $diff_alpha;
		}

		$alpha[$max_kkt_i] = $alpha[$max_kkt_i] + $add_alpha;

		if(!($is_computed[$max_kkt_i]))
		{
			for($i=0;$i<$K;$i++)
			{
				$A[$i][$max_kkt_i] = Features::dotProduct($a->[$i],$a->[$max_kkt_i]);
				$is_computed[$max_kkt_i] = 1;
			}
		}
		
		for($i=0;$i<$K;$i++)
		{
			$F[$i] -= $add_alpha * $A[$i][$max_kkt_i];
			$kkt[$i] = $F[$i];
			if($alpha[$i] > $zero)
			{
				if($F[$i]<0)
				{ $kkt[$i] = -$F[$i]; }
				else
				{ $kkt[$i] = $F[$i]; }
			}
		}

		$max_kkt = -100000;
		$max_kkt_i = -1;
		
		for($i=0;$i<$K;$i++)
		{
			if($kkt[$i] > $max_kkt)
			{ $max_kkt = $kkt[$i]; $max_kkt_i = $i; }	
		}

		$iter ++; 
	}

	return @alpha;
}

sub train {

	my($corpus) = shift;
	my($Parameters) = shift;
	my $senNum;

	my($AvgParams) = new Parameters;
	my($updatedParams);

	my($prevclassacc)=-1;
	my($currclassacc);

	my($i,$j);
	my($newK);


	for($i=$C{'prevIter'};$i<$C{'targetIter'};$i++)
	{
		my($TempParams) = new Parameters;

		foreach $senNum (sort {$a<=>$b} keys %$corpus) {

			if($C{'senTrain'} < $senNum) { 
				last; 
			}

			print STDERR "Iteration $i SenId $j SenNum $senNum\n";

#			print STDERR "Predicting and Updating parameters $senNum\n";
			if($C{'trainAlgo'}==1) {
				$newK = $corpus->predictAndupdate1($senNum,$Parameters,1);
			}
			else {
				$newK = $corpus->predictAndupdate2($senNum,$Parameters,1);
			}

			$AvgParams->addparams($Parameters);

#print STDERR "\n\n";

		}	


		# Store the parameters which have not been averaged yet
		# print STDERR "Storing Parameter Values in a File\n";
		$AvgParams->store("UnavgModelPars/$C{'paramFileUAvgOut'}.$i.temp");

		$TempParams->copy($AvgParams);
#		$TempParams->average(($i+1)*(50));
		$TempParams->average(($i+1)*(scalar(keys %$corpus)));
		$TempParams->store("AvgModelPars/$C{'paramFileOut'}.$Titerations");

	}

	$AvgParams->store($C{'paramFileUAvgOut'});

	#$AvgParams->average($C{'targetIter'}*(scalar(keys %$corpus)));
	$AvgParams->average($C{'targetIter'}*($C{'senTrain'}));
	$AvgParams->store($C{'paramFileOut'});

}

sub test {
	my($corpus) = shift;
	my($Parameters) = shift;
	
	my($K) = shift;
	my($newK);

	my($i,$j,$t);
	my($nFeatures);

	foreach $senNum (sort {$a<=>$b} keys %$corpus) {
		print STDERR "Testing:",$senNum,"\n";

		if($C{'testAlgo'}==2) {
			$newK = $corpus->predictAndupdate2($senNum,$Parameters,0);
		}
		else {
			$newK = $corpus->predictAndupdate1($senNum,$Parameters,0);
		}

		$corpus->printAlns($senNum);

#		print $senNum."\n";
#		$corpus->{$senNum}->{'AlignBeam'}->[0]->print($corpus->{$senNum}->{'SSen'});

=cut
		print STDERR "ENGSEN :";
		for($t=0;$t<=$#{$corpus->{$senNum}->{'SSen'}};$t++)
		{ print STDERR $t.".".$this->[$j]->{'SSen'}->{'word'}->[$t]."/".$this->[$j]->{'SSen'}->{'pos'}->[$t]." "; }
		print STDERR "\n";
		print STDERR "HINSEN :";
		for($t=0;$t<=$#{$this->[$j]->{'TSen'}->{'word'}};$t++)
		{ print STDERR $t.".".$this->[$j]->{'TSen'}->{'word'}->[$t]."/".$this->[$j]->{'TSen'}->{'pos'}->[$t]." "; }
		print STDERR "\n";

		$corpus->printparallel($senNum,$newK);
=cut
	}
		

}

sub printAlns {
	my($corpus) = shift;
	my($senNum) = shift;
	my($engsen);
	my($i,$k);

	$engsen = $corpus->{$senNum}->{'SSen'};

	my($predictAln) = $corpus->{$senNum}->{'AlignBeam'}->[0];

	for($i=0;$i<@{$engsen};$i++) {
		foreach $k (@{$predictAln->{'aln'}->[$i]}) {
			print "$senNum\t$i\t$k\n";
		}
	}
}

sub printparallel {
	my($this) = shift;  # Of type $this->[$j]
	my($i,$j,$k);
	$j=shift;
	my($K) = shift;
	my($engsen);
	#print "---------\n";
	#for($j=0;$j<=$#$this;$j++)  
	#{
		#print "SenNum = $j "..$this->[$j]->{'SenNum'}."\n";
		$engsen = $this->[$j]->{'SSen'};
		for($i=0;$i<=$#{$engsen->{'word'}};$i++)
		{

			#if($i<=9) { print STDERR "0"; }
			print STDERR "$i => ";
			#if($this->[$j]->{'Align'}->{'aln'}->[$i] eq "-")
			#{ print STDERR "-"; }
			#elsif($this->[$j]->{'Align'}->{'aln'}->[$i]<=9)
			#{ print STDERR "0"; }
#			print STDERR $this->[$j]->{'Align'}->{'aln'}->[$i]."\t";
			my(%variations);
			for($k=0;$k<$K;$k++)
			{
			
				#print STDERR "\t";
				#if($this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i] eq "-")
				#{ print STDERR "-"; }
				#elsif($this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]<=9)
				#{ print STDERR "0"; }
				#print STDERR $this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]."/".&r($this->[$j]->{'AlignBeam'}->[$k]->{'alnscr'}->[$i],1); 

				$var = $this->[$j]->{'AlignBeam'}->[$k]->{'aln'}->[$i]."/".&r($this->[$j]->{'AlignBeam'}->[$k]->{'alnscr'}->[$i],1);
				if($k==0) { $var="*".$var; $variations{$var}=1; }
				elsif(!($variations{"*".$var}))
				{ $variations{$var} = 1; }
			}
			$varstr = "";
			foreach $var (sort {$a <=> $b} keys %variations)
			{	
				$varstr .= $var." ";
			}
#			print STDERR $varstr;
			print STDERR "\n";
			undef($variations)
	
		}	
		#print STDERR "Scr => .";
		#for($k=0;$k<$K;$k++)
		#{
		#	print STDERR "\t   ".&r($this->[$j]->{'AlignBeam'}->[$k]->{'score'},1);
		#}
		print STDERR "\n---------\n\n";
	#}
}

sub getAccuracy {
	my($this) = shift;
	my($total) = 0;
	my($correct) = 0;
	my($a,$b);

	for($j=0;$j<=$#$this;$j++)  
	{
		($a,$b) = $this->[$j]->{'Align'}->getCorrects($this->[$j]->{'AlignBeam'}->[0]);
		$total+=$b;
		$correct+=$a;	
	}	

	return $correct*100/$total;
}

sub r {
    my ($number,$decimals) = @_;
    return substr($number+("0."."0"x$decimals."5"),
                  0, $decimals+length(int($number))+1);
}


1;
